Dynamic programming algorithms

Any question about the previous lecture?

Historic hero: Fibonacci

He was a mathematician

First person to introduce in Europe the Hindu-Arabic number system (i.e. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

Publication Liber Abaci (Book of Calculation) in 1202: how to use such numeral system for addressing situations related to commerce, and for solving generic mathematical problems

Fibonacci sequence

Fibonacci developed an infinite sequence of numbers, named after him, that described ideally the number of male-female pairs of rabbits at a given month

fib(0) = 0 [base case 1]

fib(1) = 1 [base case 2]

fib(n) = fib(n-1) + fib(n-2) [recursive step]

Fibonacci (divide and conquer): algorithm

def fib_dc(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_dc(n-1) + fib_dc(n-2)

Dynamic programming approach

Dynamic programming algorithm is based on six steps

1. [base case: solution exists] return the solution calculated previously, otherwise

2. [base case: address directly] address directly if it is an easy-to-solve problem, otherwise

3. [divide] split the input material into two or more balanced parts, each depicting a sub-problem of the original one

4. [conquer] run the same algorithm recursively for every balanced parts obtained in the previous step

5. [combine] reconstruct the final solution of the problem by means of the partial solutions

6. [memorize] store the solution to the problem for reusing it

Fibonacci: ancillary operation

Non-inclusion in dictionary:
<key> not in <dictionary>

Comparison that returns True if <key> is not included as key in any pair of <dictionary>

Fibonacci (dynamic programming): algorithm

def fib_dp(n, d):
    if n not in d:
        if n <= 0:
            d[n] = 0
        elif n == 1:
            d[n] = 1
        else:
            d[n] = fib_dp(n-1, d) + fib_dp(n-2, d)

    return d.get(n)